#pragma once

#include <string>
using std::string;

class exception
{
public:
	exception(int id, const string& errmsg);

	string what() const;

protected:
	int m_errid;
	string m_errmsg;
};


class matrix_coordinate_invalid : public exception
{
public:
	matrix_coordinate_invalid(const string& errmsg, int id = 1);
};

class matrix_multiplication_error : public exception
{
public:
	matrix_multiplication_error(const string& errmsg, int id = 2);
};

class matrix_addition_error : public exception
{
public:
	matrix_addition_error(const string& errmsg, int id = 3);
};



exception::exception(int id, const string& errmsg)
	: m_errid(id)
	, m_errmsg(errmsg)
{

}

string exception::what() const
{
	return m_errmsg;
}

matrix_coordinate_invalid::matrix_coordinate_invalid(const string& errmsg, int id)
	: exception(id, errmsg)
{

}

matrix_multiplication_error::matrix_multiplication_error(const string& errmsg, int id)
	: exception(id, errmsg)
{

}

matrix_addition_error::matrix_addition_error(const string& errmsg, int id)
	: exception(id, errmsg)
{

}

#pragma once

#include <vector>
using std::vector;

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <utility>



// 凡是在矩阵中的位置都以(1, 1)开始, 只有在存储中的位置才以0开始, 注意两种表述的不同, 此后不在强调

struct sparse_matrix_term
{
	// 位置信息
	int m_row;
	int m_col;
	// 数据信息
	int m_data;

	sparse_matrix_term(int row = 0, int col = 0, const int& data = 0);

	bool isvalid(int matrix_row, int matrix_col) const;
};

// 稀疏矩阵: COO压缩算法, 行存储
class sparse_matrix
{
public:
	// 默认构造
	sparse_matrix(int row = 0, int col = 0, int size = 0);

	// 拷贝构造
	sparse_matrix(const sparse_matrix& m2);

	// 清空
	void clear();

	// 赋值重载
	sparse_matrix& operator=(const sparse_matrix& x);

	// 析构, 不需要自定义

	// 添加元素
	void push(const sparse_matrix_term& term);

	// 修改sparse matrix的行列值
	void set_row_col(int row, int col);

	// 两个稀疏矩阵相加, 非直接或间接转换为二维数组形式计算
	/*
		有关两个稀疏矩阵相加算法的直观想象:
		想象两个完整的矩阵, 将这两个稀疏矩阵的非零元素标出来
		从第一行开始对两个矩阵同时进行逐行扫描, 遇到非零元素, 就相加到新矩阵中
	*/
	sparse_matrix operator+(const sparse_matrix& m2);
	sparse_matrix add(const sparse_matrix& m2);
	sparse_matrix& operator+=(const sparse_matrix& m2);

	// 稀疏矩阵的转置, CSR
	/*
		法一: 按列进制数排序: 时间复杂度O(n^2); 当然使用桶排序/基数排序会将时间复杂度降为O(n)
		法二: 课本, 和桶排序有一样的限制, 如果一列元素很多数组存不下怎么办
	*/
	void transpose();

	// 矩阵乘法, 不直接或间接转换为二维数组形式计算
	/*
		法一: 常规方法的变式, 创建一个col个累加器, 一遍循环算出结果矩阵的一行
		法二, 高性能: CSR
	*/
	// CSR算法
	sparse_matrix& operator*=(const sparse_matrix& m2);


	// 获取在矩阵中位置为(row, col)的元素. 凡是写在矩阵中, 都是以(1,1)开始
	int get(int row, int col) const;

	// 输出矩阵, 以普通矩阵的形式
	void show();

private:
	// 矩阵的大小信息
	int m_row;
	int m_col;
	// 非零元素的信息, 行主映射
	vector<sparse_matrix_term> m_terms;
};

// 利用一个普通矩阵初始化稀疏矩阵
// 输入: 矩阵的行数n 矩阵的列数m 一个普通矩阵
void init_sparse_matrix_by_matrix(sparse_matrix& x);

// 利用非零元素初始化稀疏矩阵
// 输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
void init_sparse_matrix_by_nonzero_elements(sparse_matrix& x);



sparse_matrix_term::sparse_matrix_term(int row, int col, const int& data)
	: m_row(row)
	, m_col(col)
	, m_data(data)
{

}

bool sparse_matrix_term::isvalid(int matrix_row, int matrix_col) const
{
	if (m_col <= matrix_col && m_col >= 1 && m_row >= 1 && m_row <= matrix_row)
	{
		return true;
	}

	return false;
}

// 默认构造
sparse_matrix::sparse_matrix(int row, int col, int size)
	: m_row(row)
	, m_col(col)
	, m_terms(size, 0)
{

}

// 拷贝构造
sparse_matrix::sparse_matrix(const sparse_matrix& m2)
{
	m_row = m2.m_row;
	m_col = m2.m_col;
	m_terms = m2.m_terms;

}

// 清空
void sparse_matrix::clear()
{
	m_row = 0;
	m_col = 0;
	m_terms.clear();
}

// 赋值重载
sparse_matrix& sparse_matrix::operator=(const sparse_matrix& x)
{
	if (this != &x)
	{
		m_row = x.m_row;
		m_col = x.m_col;
		m_terms = x.m_terms;
	}

	return *this;
}

// 析构, 不需要自定义

// 添加元素
void sparse_matrix::push(const sparse_matrix_term& term)
{
	if (!term.isvalid(m_row, m_col))
	{
		throw matrix_coordinate_invalid("term coordinate invalid");
	}

	m_terms.push_back(term);
}

// 修改sparse matrix的行列值
void sparse_matrix::set_row_col(int row, int col)
{
	m_row = row;
	m_col = col;
}

// 两个稀疏矩阵相加, 非直接或间接转换为二维数组形式计算
/*
	有关两个稀疏矩阵相加算法的直观想象:
	想象两个完整的矩阵, 将这两个稀疏矩阵的非零元素标出来
	从第一行开始对两个矩阵同时进行逐行扫描, 遇到非零元素, 就相加到新矩阵中
*/
sparse_matrix sparse_matrix::operator+(const sparse_matrix& m2)
{
	sparse_matrix sum(m_row, m_col);
	sum += *this;
	sum += m2;
	return sum;
}

sparse_matrix sparse_matrix::add(const sparse_matrix& m2)
{
	if (m_row != m2.m_row || m_col != m2.m_col)
	{
		throw matrix_addition_error("maxtri addition error");
	}

	sparse_matrix sum(m_row, m_col);
	for (int i = 1; i <= m_row; ++i)
	{
		for (int j = 1; j <= m_col; ++j)
		{
			if (get(i, j) + m2.get(i, j) != 0)
			{
				sum.push(sparse_matrix_term(i, j, get(i, j) + m2.get(i, j)));
			}

		}
	}

	return sum;
}



sparse_matrix& sparse_matrix::operator+=(const sparse_matrix& m2)
{
	// 检查加法的合法性
	if (m_row != m2.m_row || m_col != m2.m_col)
	{
		throw matrix_addition_error("maxtri addition error");
	}

	// 对矩阵中的每一个元素进行, 行优先, 标号, 1,2,3...., 
	// 把矩阵看做一行

	sparse_matrix sum(m_row, m_col);
	
	int m1_count = 0;
	int m2_count = 0;
	while (m1_count < m_terms.size() && m2_count < m2.m_terms.size())
	{
		int m1_idx = (m_terms[m1_count].m_row - 1) * m_col + m_terms[m1_count].m_col;
		int m2_idx = (m2.m_terms[m2_count].m_row - 1) * m_col + m2.m_terms[m2_count].m_col;

		if (m1_idx < m2_idx)
		{
			sum.push(m_terms[m1_count]);
			++m1_count;
		}
		else if (m1_idx > m2_idx)
		{
			sum.push(m2.m_terms[m2_count]);
			++m2_count;
		}
		else
		{
			if (m_terms[m1_count].m_data + m2.m_terms[m2_count].m_data != 0)
			{
				sparse_matrix_term tmp(m_terms[m1_count].m_row, m_terms[m1_count].m_col, m_terms[m1_count].m_data + m2.m_terms[m2_count].m_data);
				sum.push(tmp);
				
			}

			++m1_count;
			++m2_count;
		}

	}

	while (m1_count < m_terms.size())
	{
		sum.push(m_terms[m1_count]);
		++m1_count;
	}

	while (m2_count < m2.m_terms.size())
	{
		sum.push(m2.m_terms[m2_count]);
		++m2_count;
	}

	m_terms.swap(sum.m_terms);

	return *this;
}

// 稀疏矩阵的转置, CSR
/*
	法一: 按列进制数排序: 时间复杂度O(n^2); 当然使用桶排序/基数排序会将时间复杂度降为O(n)
	法二: 课本, 和桶排序有一样的限制, 如果一列元素很多数组存不下怎么办
*/
void sparse_matrix::transpose()
{
	sparse_matrix m_T(m_col, m_row, m_terms.size()); // 记录转置之后的矩阵

	// 转置前矩阵各个列的非零元素的个数, 即是转置后各个行的非零元素的个数
	vector<int> count_non_zero_per_row(m_col + 1, 0); // 先初始化成零
	// 这遍历的是稀疏矩阵的所有元素. 这就是为什么开辟空间要m_col+1的原因, 不想过多的在通过计算转换
	for (int i = 0; i < m_terms.size(); ++i)
	{
		++count_non_zero_per_row[m_terms[i].m_col];
	}

	// 通过count_non_zero_per_row可以计算出转置之后矩阵各行第一个非零元素, 按行主存储, 在数组中的存储位置
	// 在数组中的存储位置 f(head_element_per_row) = 前面的行已经存放的元素个数 + 1 - 1
	vector<int> start_index_per_row(m_T.m_row + 1, 0);
	// 通过计算count_non_zero_per_row的累积和得到前面的行已经存放的元素个数
	int accumulation = count_non_zero_per_row[1];
	for (int i = 2; i <= m_T.m_row; ++i)
	{
		start_index_per_row[i] = accumulation;
		accumulation += count_non_zero_per_row[i];
	}

	// 进行转置矩阵的非零元素的数据载入
	for (int i = 0; i < m_terms.size(); ++i)
	{
		// 1. 每个元素的行列互换 2. 有效性证明, 矩阵转置的直观定义
		/*
			转置前矩阵的m_terms[i]元素, 在转置后矩阵的存储位置为:
			它在转置后矩阵中的位置为(m_terms[i].col, m_terms[i].row),
			那么其存储位置为start_index_per_row[m_terms[i].col] + 这一行已经存储的元素个数
			可以转化成每次存一个元素后就++
		*/
		int idx = start_index_per_row[m_terms[i].m_col];
		m_T.m_terms[idx] = sparse_matrix_term(m_terms[i].m_col, m_terms[i].m_row, m_terms[i].m_data);
		++start_index_per_row[m_terms[i].m_col];
	}

	std::swap(m_T.m_row, m_row);
	std::swap(m_T.m_col, m_col);
	m_terms.swap(m_T.m_terms);
}

// 矩阵乘法, 不直接或间接转换为二维数组形式计算
/*
	法一: 常规方法的变式, 创建一个col个累加器, 一遍循环算出结果矩阵的一行
	法二, 高性能: CSR
*/
// CSR算法
#pragma once

#include <string>
using std::string;

class exception
{
public:
	exception(int id, const string& errmsg);

	string what() const;

protected:
	int m_errid;
	string m_errmsg;
};


class matrix_coordinate_invalid : public exception
{
public:
	matrix_coordinate_invalid(const string& errmsg, int id = 1);
};

class matrix_multiplication_error : public exception
{
public:
	matrix_multiplication_error(const string& errmsg, int id = 2);
};

class matrix_addition_error : public exception
{
public:
	matrix_addition_error(const string& errmsg, int id = 3);
};



exception::exception(int id, const string& errmsg)
	: m_errid(id)
	, m_errmsg(errmsg)
{

}

string exception::what() const
{
	return m_errmsg;
}

matrix_coordinate_invalid::matrix_coordinate_invalid(const string& errmsg, int id)
	: exception(id, errmsg)
{

}

matrix_multiplication_error::matrix_multiplication_error(const string& errmsg, int id)
	: exception(id, errmsg)
{

}

matrix_addition_error::matrix_addition_error(const string& errmsg, int id)
	: exception(id, errmsg)
{

}

#pragma once

#include <vector>
using std::vector;

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <utility>



// 凡是在矩阵中的位置都以(1, 1)开始, 只有在存储中的位置才以0开始, 注意两种表述的不同, 此后不在强调

struct sparse_matrix_term
{
	// 位置信息
	int m_row;
	int m_col;
	// 数据信息
	int m_data;

	sparse_matrix_term(int row = 0, int col = 0, const int& data = 0);

	bool isvalid(int matrix_row, int matrix_col) const;
};

// 稀疏矩阵: COO压缩算法, 行存储
class sparse_matrix
{
public:
	// 默认构造
	sparse_matrix(int row = 0, int col = 0, int size = 0);

	// 拷贝构造
	sparse_matrix(const sparse_matrix& m2);

	// 清空
	void clear();

	// 赋值重载
	sparse_matrix& operator=(const sparse_matrix& x);

	// 析构, 不需要自定义

	// 添加元素
	void push(const sparse_matrix_term& term);

	// 修改sparse matrix的行列值
	void set_row_col(int row, int col);

	// 两个稀疏矩阵相加, 非直接或间接转换为二维数组形式计算
	/*
		有关两个稀疏矩阵相加算法的直观想象:
		想象两个完整的矩阵, 将这两个稀疏矩阵的非零元素标出来
		从第一行开始对两个矩阵同时进行逐行扫描, 遇到非零元素, 就相加到新矩阵中
	*/
	sparse_matrix operator+(const sparse_matrix& m2);
	sparse_matrix add(const sparse_matrix& m2);
	sparse_matrix& operator+=(const sparse_matrix& m2);

	// 稀疏矩阵的转置, CSR
	/*
		法一: 按列进制数排序: 时间复杂度O(n^2); 当然使用桶排序/基数排序会将时间复杂度降为O(n)
		法二: 课本, 和桶排序有一样的限制, 如果一列元素很多数组存不下怎么办
	*/
	void transpose();

	// 矩阵乘法, 不直接或间接转换为二维数组形式计算
	/*
		法一: 常规方法的变式, 创建一个col个累加器, 一遍循环算出结果矩阵的一行
		法二, 高性能: CSR
	*/
	// CSR算法
	sparse_matrix& operator*=(const sparse_matrix& m2);


	// 获取在矩阵中位置为(row, col)的元素. 凡是写在矩阵中, 都是以(1,1)开始
	int get(int row, int col) const;

	// 输出矩阵, 以普通矩阵的形式
	void show();

private:
	// 矩阵的大小信息
	int m_row;
	int m_col;
	// 非零元素的信息, 行主映射
	vector<sparse_matrix_term> m_terms;
};

// 利用一个普通矩阵初始化稀疏矩阵
// 输入: 矩阵的行数n 矩阵的列数m 一个普通矩阵
void init_sparse_matrix_by_matrix(sparse_matrix& x);

// 利用非零元素初始化稀疏矩阵
// 输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
void init_sparse_matrix_by_nonzero_elements(sparse_matrix& x);



sparse_matrix_term::sparse_matrix_term(int row, int col, const int& data)
	: m_row(row)
	, m_col(col)
	, m_data(data)
{

}

bool sparse_matrix_term::isvalid(int matrix_row, int matrix_col) const
{
	if (m_col <= matrix_col && m_col >= 1 && m_row >= 1 && m_row <= matrix_row)
	{
		return true;
	}

	return false;
}

// 默认构造
sparse_matrix::sparse_matrix(int row, int col, int size)
	: m_row(row)
	, m_col(col)
	, m_terms(size, 0)
{

}

// 拷贝构造
sparse_matrix::sparse_matrix(const sparse_matrix& m2)
{
	m_row = m2.m_row;
	m_col = m2.m_col;
	m_terms = m2.m_terms;

}

// 清空
void sparse_matrix::clear()
{
	m_row = 0;
	m_col = 0;
	m_terms.clear();
}

// 赋值重载
sparse_matrix& sparse_matrix::operator=(const sparse_matrix& x)
{
	if (this != &x)
	{
		m_row = x.m_row;
		m_col = x.m_col;
		m_terms = x.m_terms;
	}

	return *this;
}

// 析构, 不需要自定义

// 添加元素
void sparse_matrix::push(const sparse_matrix_term& term)
{
	if (!term.isvalid(m_row, m_col))
	{
		throw matrix_coordinate_invalid("term coordinate invalid");
	}

	m_terms.push_back(term);
}

// 修改sparse matrix的行列值
void sparse_matrix::set_row_col(int row, int col)
{
	m_row = row;
	m_col = col;
}

// 两个稀疏矩阵相加, 非直接或间接转换为二维数组形式计算
/*
	有关两个稀疏矩阵相加算法的直观想象:
	想象两个完整的矩阵, 将这两个稀疏矩阵的非零元素标出来
	从第一行开始对两个矩阵同时进行逐行扫描, 遇到非零元素, 就相加到新矩阵中
*/
sparse_matrix sparse_matrix::operator+(const sparse_matrix& m2)
{
	sparse_matrix sum(m_row, m_col);
	sum += *this;
	sum += m2;
	return sum;
}

sparse_matrix sparse_matrix::add(const sparse_matrix& m2)
{
	if (m_row != m2.m_row || m_col != m2.m_col)
	{
		throw matrix_addition_error("maxtri addition error");
	}

	sparse_matrix sum(m_row, m_col);
	for (int i = 1; i <= m_row; ++i)
	{
		for (int j = 1; j <= m_col; ++j)
		{
			if (get(i, j) + m2.get(i, j) != 0)
			{
				sum.push(sparse_matrix_term(i, j, get(i, j) + m2.get(i, j)));
			}

		}
	}

	return sum;
}



sparse_matrix& sparse_matrix::operator+=(const sparse_matrix& m2)
{
	// 检查加法的合法性
	if (m_row != m2.m_row || m_col != m2.m_col)
	{
		throw matrix_addition_error("maxtri addition error");
	}

	// 对矩阵中的每一个元素进行, 行优先, 标号, 1,2,3...., 
	// 把矩阵看做一行

	sparse_matrix sum(m_row, m_col);
	
	int m1_count = 0;
	int m2_count = 0;
	while (m1_count < m_terms.size() && m2_count < m2.m_terms.size())
	{
		int m1_idx = (m_terms[m1_count].m_row - 1) * m_col + m_terms[m1_count].m_col;
		int m2_idx = (m2.m_terms[m2_count].m_row - 1) * m_col + m2.m_terms[m2_count].m_col;

		if (m1_idx < m2_idx)
		{
			sum.push(m_terms[m1_count]);
			++m1_count;
		}
		else if (m1_idx > m2_idx)
		{
			sum.push(m2.m_terms[m2_count]);
			++m2_count;
		}
		else
		{
			if (m_terms[m1_count].m_data + m2.m_terms[m2_count].m_data != 0)
			{
				sparse_matrix_term tmp(m_terms[m1_count].m_row, m_terms[m1_count].m_col, m_terms[m1_count].m_data + m2.m_terms[m2_count].m_data);
				sum.push(tmp);
				
			}

			++m1_count;
			++m2_count;
		}

	}

	while (m1_count < m_terms.size())
	{
		sum.push(m_terms[m1_count]);
		++m1_count;
	}

	while (m2_count < m2.m_terms.size())
	{
		sum.push(m2.m_terms[m2_count]);
		++m2_count;
	}

	m_terms.swap(sum.m_terms);

	return *this;
}

// 稀疏矩阵的转置, CSR
/*
	法一: 按列进制数排序: 时间复杂度O(n^2); 当然使用桶排序/基数排序会将时间复杂度降为O(n)
	法二: 课本, 和桶排序有一样的限制, 如果一列元素很多数组存不下怎么办
*/
void sparse_matrix::transpose()
{
	sparse_matrix m_T(m_col, m_row, m_terms.size()); // 记录转置之后的矩阵

	// 转置前矩阵各个列的非零元素的个数, 即是转置后各个行的非零元素的个数
	vector<int> count_non_zero_per_row(m_col + 1, 0); // 先初始化成零
	// 这遍历的是稀疏矩阵的所有元素. 这就是为什么开辟空间要m_col+1的原因, 不想过多的在通过计算转换
	for (int i = 0; i < m_terms.size(); ++i)
	{
		++count_non_zero_per_row[m_terms[i].m_col];
	}

	// 通过count_non_zero_per_row可以计算出转置之后矩阵各行第一个非零元素, 按行主存储, 在数组中的存储位置
	// 在数组中的存储位置 f(head_element_per_row) = 前面的行已经存放的元素个数 + 1 - 1
	vector<int> start_index_per_row(m_T.m_row + 1, 0);
	// 通过计算count_non_zero_per_row的累积和得到前面的行已经存放的元素个数
	int accumulation = count_non_zero_per_row[1];
	for (int i = 2; i <= m_T.m_row; ++i)
	{
		start_index_per_row[i] = accumulation;
		accumulation += count_non_zero_per_row[i];
	}

	// 进行转置矩阵的非零元素的数据载入
	for (int i = 0; i < m_terms.size(); ++i)
	{
		// 1. 每个元素的行列互换 2. 有效性证明, 矩阵转置的直观定义
		/*
			转置前矩阵的m_terms[i]元素, 在转置后矩阵的存储位置为:
			它在转置后矩阵中的位置为(m_terms[i].col, m_terms[i].row),
			那么其存储位置为start_index_per_row[m_terms[i].col] + 这一行已经存储的元素个数
			可以转化成每次存一个元素后就++
		*/
		int idx = start_index_per_row[m_terms[i].m_col];
		m_T.m_terms[idx] = sparse_matrix_term(m_terms[i].m_col, m_terms[i].m_row, m_terms[i].m_data);
		++start_index_per_row[m_terms[i].m_col];
	}

	std::swap(m_T.m_row, m_row);
	std::swap(m_T.m_col, m_col);
	m_terms.swap(m_T.m_terms);
}

// 矩阵乘法, 不直接或间接转换为二维数组形式计算
/*
	法一: 常规方法的变式, 创建一个col个累加器, 一遍循环算出结果矩阵的一行
	法二, 高性能: CSR
*/
// CSR算法
sparse_matrix& sparse_matrix::operator*=(const sparse_matrix& m2)
{
	// 检查乘法的合法性
	if (!(m_col == m2.m_row))
	{
		throw matrix_multiplication_error("maxtri multiplication error");
	}

	// this即是m1
	// m1每行的元素个数
	vector<int> m1_row_count(m_row + 1, 0);
	for (int i = 0; i < m_terms.size(); ++i)
	{
		++m1_row_count[m_terms[i].m_row];
	}
	// m1的行指针数组rowidx
	vector<int> m1_rowidx(m_row + 1, 0);
	int m1_cumulative_sum = m1_row_count[1];
	for (int i = 2; i <= m_row; ++i)
	{
		m1_rowidx[i] = m1_cumulative_sum;
		m1_cumulative_sum += m1_row_count[i];
	}

	// m2
	// m2每行的元素个数, 使用的方法是计数数组
	vector<int> m2_row_count(m2.m_row + 1, 0);
	for (int i = 0; i < m2.m_terms.size(); ++i)
	{
		++m2_row_count[m2.m_terms[i].m_row];
	}
	// m2的行指针数组rowidx
	vector<int> m2_rowidx(m2.m_row + 1, 0);
	int m2_cumulative_sum = m2_row_count[1];
	for (int i = 2; i <= m_row; ++i)
	{
		m2_rowidx[i] = m2_cumulative_sum;
		m2_cumulative_sum += m2_row_count[i];
	}

	sparse_matrix product(m_row, m2.m_col);

	vector<int> row_sum_array(m2.m_col + 1, 0);
	//row_sum_array.resize(m2.m_col + 1);

	// 求结果矩阵的第i行的非零元素 = m1的第i行的各个元素 * m2的对应行 (列与行对应), 再求和
	for (int i = 1; i <= product.m_row; ++i)
	{
		// 遍历m1的第i行的非零元素, j是存储索引
		for (int j = m1_rowidx[i]; j < m1_rowidx[i] + m1_row_count[i]; ++j)
		{
			// m1第i行 m_terms[j]的非零元素, 其所在列为k = m_terms[j].m_col, 即m1的第i行第k个元素, 与m2的第k行的各个元素相乘
			int k = m_terms[j].m_col;

			// 遍历m2的第k行的非零元素, p是存储索引
			for (int p = m2_rowidx[k]; p < m2_rowidx[k] + m2_row_count[k]; ++p)
			{
				// m2第k行 m2.m_terms[p]非零元素, 其所在列为s = m2.m_terms[p].m_col, 即m2的第k行的第s个元素, 与m1第i行的第k个元素相乘, 
				// 得到结果矩阵(i, s)元素的分量

				int s = m2.m_terms[p].m_col;
				// 结果矩阵(i, p)元素的分项
				row_sum_array[s] += m_terms[j].m_data * m2.m_terms[p].m_data;
			}
		}

		if (m1_row_count[i] != 0)
		{
			for (int c = 1; c <= m2.m_col; ++c)
			{
				if (row_sum_array[c] != 0)
				{
					product.push(sparse_matrix_term(i, c, row_sum_array[c]));
					row_sum_array[c] = 0;
				}

			}
		}
		

		
		
	}

	m_row = product.m_row;
	m_col = product.m_col;
	m_terms.swap(product.m_terms);

	return *this;
}



// 获取在矩阵中位置为(row, col)的元素. 凡是写在矩阵中, 都是以(1,1)开始
int sparse_matrix::get(int row, int col) const
{
	if (!(row >= 1 && row <= m_row && col >= 1 && col <= m_col))
	{
		throw matrix_coordinate_invalid("coordinate invalid");
	}

	for (int i = 0; i < m_terms.size(); ++i)
	{
		if (m_terms[i].m_row == row && m_terms[i].m_col == col)
		{
			return m_terms[i].m_data;
		}
		else if (m_terms[i].m_row > row)
		{
			break;
		}
		else if (m_terms[i].m_row == row && m_terms[i].m_col > col)
		{
			break;
		}
	}

	return 0; // 这一点就受限了该类的数据类型只能为数值型
}

// 输出矩阵, 以普通矩阵的形式
void sparse_matrix::show()
{
	cout << m_row << " " << m_col << endl;
	int k = 0;
	for (int i = 1; i <= m_row; ++i)
	{
		for (int j = 1; j <= m_col; ++j)
		{
			// cout << get(i, j) << " "; 这样做会变成n^3的时间复杂度
			// 为什么要加k < m_terms.size()??, 会越界
			if (k < m_terms.size() && m_terms[k].m_row == i && m_terms[k].m_col == j)
			{
				cout << m_terms[k].m_data << " ";
				k++;
			}
			else
			{
				cout << 0 << " ";
			}

		}
		cout << endl;
	}
}

// 利用一个普通矩阵初始化稀疏矩阵
// 输入: 矩阵的行数n 矩阵的列数m 一个普通矩阵
void init_sparse_matrix_by_matrix(sparse_matrix& x)
{
	x.clear();
	int row = 0;
	int col = 0;
	cin >> row >> col;
	x.set_row_col(row, col);

	int val = 0;
	for (int i = 1; i <= row; ++i)
	{
		for (int j = 1; j <= col; ++j)
		{
			cin >> val;
			if (val != 0)
			{
				x.push(sparse_matrix_term(i, j, val));
			}
		}
	}

}

// 利用非零元素初始化稀疏矩阵
// 输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
void init_sparse_matrix_by_nonzero_elements(sparse_matrix& x)
{
	x.clear();
	int row = 0;
	int col = 0;
	int non_zero_num = 0; // 非零元素个数
	cin >> row >> col >> non_zero_num;
	x.set_row_col(row, col);

	// 载入非零元素
	int e_row = 0;
	int e_col = 0;
	int e_val = 0;
	for (int i = 0; i < non_zero_num; ++i)
	{
		cin >> e_row >> e_col >> e_val;
		x.push(sparse_matrix_term(e_row, e_col, e_val));
	}
}




void solution()
{
	// 输入: 操作个数 
	int op_num = 0;
	cin >> op_num;

	// 执行, 规定第一个操作为重置矩阵
	int opcode = 0; // 操作码
	sparse_matrix m1;

	for (int i = 0; i < op_num; ++i)
	{
		cin >> opcode;

		switch (opcode)
		{
			/*
				重置矩阵 1:
					输入: 矩阵的行数n 矩阵的列数m 一个普通矩阵

					执行: 按COO压缩算法存储该矩阵
			*/
			case 1:
			{
				init_sparse_matrix_by_matrix(m1);
				break;
			}
			/*
				矩阵乘法 2:
					输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
							按行优先给出t个非零元素的COO三元组

					执行以及输出: 设输入的矩阵为m2,若运算合法,则将运算结果矩阵赋给m1,若不合法,则将m2赋给m1, 输出 -1。
			*/
			case 2:
			{
				sparse_matrix m2;
				init_sparse_matrix_by_nonzero_elements(m2);
				try
				{
					m1 *= m2;
					//m1 = m1.add(m2);
				}
				catch (const exception& e)
				{
					m1 = m2;
					cout << -1 << endl;
				}

				break;
			}
			/*
				矩阵加法 3: 
					输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
							按行优先给出t个非零元素的COO三元组
				
					执行以及输出: 设输入的矩阵为m2,若运算合法,则将运算结果矩阵赋给m1,若不合法,则将m2赋给m1, 输出 -1。
			*/
			case 3:
			{
				sparse_matrix m2;
				init_sparse_matrix_by_nonzero_elements(m2);
				try
				{
					m1 += m2;
					
				}
				catch (const exception& e)
				{
					m1 = m2;
					cout << -1 << endl;
				}

				break;
			}
			/*
				输出操作 4, 输出一个普通矩阵
			*/
			case 4:
			{
				m1.show();
				break;
			}
			/*
				转置操作 5, 无需输出。
			*/
			case 5:
			{
				m1.transpose();
				break;
			}
		}
	}


}

int main()
{
	solution();

	return 0;
}       




// 获取在矩阵中位置为(row, col)的元素. 凡是写在矩阵中, 都是以(1,1)开始
int sparse_matrix::get(int row, int col) const
{
	if (!(row >= 1 && row <= m_row && col >= 1 && col <= m_col))
	{
		throw matrix_coordinate_invalid("coordinate invalid");
	}

	for (int i = 0; i < m_terms.size(); ++i)
	{
		if (m_terms[i].m_row == row && m_terms[i].m_col == col)
		{
			return m_terms[i].m_data;
		}
		else if (m_terms[i].m_row > row)
		{
			break;
		}
		else if (m_terms[i].m_row == row && m_terms[i].m_col > col)
		{
			break;
		}
	}

	return 0; // 这一点就受限了该类的数据类型只能为数值型
}

// 输出矩阵, 以普通矩阵的形式
void sparse_matrix::show()
{
	cout << m_row << " " << m_col << endl;
	int k = 0;
	for (int i = 1; i <= m_row; ++i)
	{
		for (int j = 1; j <= m_col; ++j)
		{
			// cout << get(i, j) << " "; 这样做会变成n^3的时间复杂度
			// 为什么要加k < m_terms.size()??, 会越界
			if (k < m_terms.size() && m_terms[k].m_row == i && m_terms[k].m_col == j)
			{
				cout << m_terms[k].m_data << " ";
				k++;
			}
			else
			{
				cout << 0 << " ";
			}

		}
		cout << endl;
	}
}

// 利用一个普通矩阵初始化稀疏矩阵
// 输入: 矩阵的行数n 矩阵的列数m 一个普通矩阵
void init_sparse_matrix_by_matrix(sparse_matrix& x)
{
	x.clear();
	int row = 0;
	int col = 0;
	cin >> row >> col;
	x.set_row_col(row, col);

	int val = 0;
	for (int i = 1; i <= row; ++i)
	{
		for (int j = 1; j <= col; ++j)
		{
			cin >> val;
			if (val != 0)
			{
				x.push(sparse_matrix_term(i, j, val));
			}
		}
	}

}

// 利用非零元素初始化稀疏矩阵
// 输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
void init_sparse_matrix_by_nonzero_elements(sparse_matrix& x)
{
	x.clear();
	int row = 0;
	int col = 0;
	int non_zero_num = 0; // 非零元素个数
	cin >> row >> col >> non_zero_num;
	x.set_row_col(row, col);

	// 载入非零元素
	int e_row = 0;
	int e_col = 0;
	int e_val = 0;
	for (int i = 0; i < non_zero_num; ++i)
	{
		cin >> e_row >> e_col >> e_val;
		x.push(sparse_matrix_term(e_row, e_col, e_val));
	}
}




void solution()
{
	// 输入: 操作个数 
	int op_num = 0;
	cin >> op_num;

	// 执行, 规定第一个操作为重置矩阵
	int opcode = 0; // 操作码
	sparse_matrix m1;

	for (int i = 0; i < op_num; ++i)
	{
		cin >> opcode;

		switch (opcode)
		{
			/*
				重置矩阵 1:
					输入: 矩阵的行数n 矩阵的列数m 一个普通矩阵

					执行: 按COO压缩算法存储该矩阵
			*/
			case 1:
			{
				init_sparse_matrix_by_matrix(m1);
				break;
			}
			/*
				矩阵乘法 2:
					输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
							按行优先给出t个非零元素的COO三元组

					执行以及输出: 设输入的矩阵为m2,若运算合法,则将运算结果矩阵赋给m1,若不合法,则将m2赋给m1, 输出 -1。
			*/
			case 2:
			{
				sparse_matrix m2;
				init_sparse_matrix_by_nonzero_elements(m2);
				try
				{
					m1 *= m2;
					//m1 = m1.add(m2);
				}
				catch (const exception& e)
				{
					m1 = m2;
					cout << -1 << endl;
				}

				break;
			}
			/*
				矩阵加法 3: 
					输入: 矩阵的行数 矩阵的列数 矩阵中非零元素个数t
							按行优先给出t个非零元素的COO三元组
				
					执行以及输出: 设输入的矩阵为m2,若运算合法,则将运算结果矩阵赋给m1,若不合法,则将m2赋给m1, 输出 -1。
			*/
			case 3:
			{
				sparse_matrix m2;
				init_sparse_matrix_by_nonzero_elements(m2);
				try
				{
					m1 += m2;
					
				}
				catch (const exception& e)
				{
					m1 = m2;
					cout << -1 << endl;
				}

				break;
			}
			/*
				输出操作 4, 输出一个普通矩阵
			*/
			case 4:
			{
				m1.show();
				break;
			}
			/*
				转置操作 5, 无需输出。
			*/
			case 5:
			{
				m1.transpose();
				break;
			}
		}
	}


}

int main()
{
	solution();

	return 0;
}       
